|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ グラフ理論 ： [ぐらふりろん] (n) graph theory ・ ラフ ： [らふ] 1. (adj,n) rough 2. (adj,n) rough ・ 理 ： [り] 【名詞】 1. reason ・ 理論 ： [りろん] 【名詞】 1. theory ・ 論 ： [ろん] 【名詞】 1. (1) argument 2. discussion 3. dispute 4. controversy 5. discourse 6. debate 7. (2) theory 8. doctrine 9. (3) essay 10. treatise 1 1. comment
グラフ理論において、グラフの道（みち）またはパス（）は、頂点の列であり、各頂点とその次の頂点との間に辺が存在する。道は無限の場合もあるが、有限な道には常に始点と終点がある。始点と終点をまとめて端子頂点 (terminal vertices) と呼び、道上の他の頂点を内部頂点 (internal vertices) と呼ぶ。閉道は始点と終点が同じ頂点となっている道である。なお、閉道においてどの頂点を始点とするかは任意である。 道と閉道はグラフ理論の基本的概念であり、グラフ理論の書籍では必ず導入部分で説明されている。例えば、Bondy and Murty (1976)、Gibbons (1985)、Diestel (2005)、Korte et al. (1990) では、道に関するより進んだアルゴリズム的項目を網羅している。 == 道の種類 == 無向グラフだけでなく、有向グラフにも道はあり、頂点の列において常に前の頂点から次の頂点へ辺が向かっている。「有向道; directed path」、「有向閉道; directed cycle」といった呼称もよく使われる。 頂点が複数回出現しない道を単純道 (simple path) と呼び、始点/終点以外の頂点が複数回出現しない閉道を単純閉道 (simple cycle) と呼ぶ。最近では "simple"（単純）は最初から含意されていることが多く、閉道と言えば単純閉道を意味し、道といえば単純道を意味する。ただし常にそういう意味で使われるとは限らない。書籍によっては（例えば Bondy and Murty 1976）、頂点が反復する道を歩道 (walk) と呼び、ここでいう単純道を道 (path) と呼んでいる。 道の上で隣接しない頂点間に辺が存在しない道を誘導道 (induced path) と呼ぶ。 グラフの全ての頂点を含む単純閉道をハミルトン閉路と呼ぶ。 共通する内部頂点を持たない2つの道は互いに「独立」、あるいは「内部頂点が互いに素 (点素)」であるという。 また、共通する内部の辺を持たない2つの道は互いに「辺素」であるという 道を構成する辺の数を道の「長さ」と呼び、複数回出現する辺は複数回カウントする。頂点が1つでも道ということができ、その場合の長さはゼロである。 重み付きグラフは各辺に値（重み）が対応しているグラフである。この場合「道の重み」は、道に属する辺の重みの総和である。重み (weight) ではなく、コスト (cost) とか長さ (length) と呼ぶこともある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「道 (グラフ理論)」の詳細全文を読む スポンサード リンク
|